In prior art networks, message distribution and data stream access are generally controlled at the message transmitting end or via centralized control apparatus and functions. Such control functions are implemented using both circuit switches and packet data switches. The following art is representative of such systems. U.S. Pat. No. 4,683,564 to Young et al. describes a matrix circuit switch system wherein a common timing signal is used to configure the system during time slices and to perform desired line connections for signal transfer during each time slice. U.S. Pat. No. 5,105,424 to Fflag et al. describes a packet routing system wherein routing and switching functions are dependent upon data contained in packet headers.
U.S. Pat. No. 4,750,171 to Kedar et al. discloses a time division multiple access system for a shared data bus wherein time slot channels are asynchronously allocated. In U.S. Pat. No. 5,008,808 to Ahmadi et al., a switching network is described that handles both voice and packet switch data and further employs uniform mini-packets which contain self-routing data. Ahmadi et al. employ uniform switching blocks that implement time slice message allocation.
U.S. Pat. No. 4,298,959 to Sundermeyer et al. describes a direct memory access message transfer system wherein asynchronously received data is stored in accordance with initially received data from the data stream. U.S. Pat. No. 4,380,046 to Fung describes a parallel processing array which employs centralized array communications control. U.S. Pat. No. 4,550,402 of Gable et al. describes a packet communication control system which enables communications between local computer networks. Two different types of mini-packets are employed with one type including header destination address data and word count information in the message portion. The second type of mini-packet includes the data message.
U.S. Pat. No. 4,623,996 to McMillen describes a packet switching node that responds to packets with routing tag signals. Lehman et al. in U.S. Pat. No. 4,763,317 describe a communication network for both narrow and wideband communications. Integrated control systems concurrently control both a narrow and wideband equipment to enable more efficient message transfer. In U.S. Pat. No. 4,811,365 to Manno, a protocol is described that enables multiple nodes to share a channel through a satellite. One node is designated as a reference node and others are designated as slave nodes, with the reference node controlling access and assuring synchronization of slave node transmissions.
U.S. Pat. No. 5,191,578 to Lee describes a parallel packet routing system which employs a scalable space-domain switching system between clusters of processors. Time domain-switching aspects are also employed to enable packet Switch-like control. Makris et al. in U.S. Pat. No. 4,979,100 describe a packet switch control network that employs an arbitration system to control message access to a bus. U.S. Pat. No. 5,117,420 to Hillis et al. disclose a message packet router that merges packets addressed to the same destination and enables broadcasting of message packets.
Presently, multi-node communication systems see many applications in data processing. For instance, parallel-processing systems include many node processors that operate in parallel upon a common problem and are interconnected by a matrix switch network. Other multi-node systems are used to perform control functions, such as controllers especially designed for use with disk drive memories. Such controllers must not only have the ability to control I/O functions, but also be able to interface with a communication network so that data from the disk drives can be distributed to requesting host processors. Within such a multi-node controller, data can be transferred at extremely high data rates (on the order of 100 megabytes per second). However, communication networks that connect such a multi-node controller to external host processors generally are able to handle data at lower transfer rates (e.g. 20 megabytes per second). As a result, input/output modules in the multi-node networks enable a "performance matching" of internal data transfer rates to the slower input/output devices that are attached to the respective nodes to enable operations without wasteful latencies. Otherwise, long messages emanating from a node in a multi-node network need to be buffered in large buffer memories that may delay and/or data starve other nodes seeking access to the input/output communication network interface. To control message delay and allocation in a multi-node network through the use of a central control mechanism or process adds significant overhead cost to the network. To allocate control of such messages strictly from the transmitting end also results in substantial network overhead. For instance, transmitting nodes are unaware of what acts are occurring at destination nodes or whether other transmitting nodes are making demands upon a destination node that is presently interfacing with the transmitting node. As a result, considerable communications are required to establish an understanding of conditions at both ends of a communication link.
Accordingly, it is an object of this invention to provide an improved system and method for enabling a multi-node network to control access of messages to an output data stream.
It is another object of this invention to provide a multi-node network with a "fairness" slicing procedure that assures all messages have at least a minimum of access to an output data stream.
It is yet another object of this invention to provide an improved data routing system for a multi-node network wherein communications overhead is distributed throughout the network.